﻿/*
给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。

 
示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4

示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2
 

提示：
1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。
*/

#include "AllInc.h"

class Solution {
public:
	int minAreaRect(vector<vector<int>>& points) 
	{
		unordered_map<int, unordered_set<int> > data;
		for (auto p : points)
		{
			data[p[0]].insert(p[1]);
		}

		int minArea = INT_MAX;
		int n = points.size();
		for (int i = 0; i < n - 1; ++i)
		{
			for (int j = i + 1; j < n; ++j)
			{
				if (points[i][0] == points[j][0] || points[i][1] == points[j][1])
				{
					continue;
				}
				if (data[points[i][0]].count(points[j][1])
					&& data[points[j][0]].count(points[i][1]))
				{
					minArea = min(minArea, 
						abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]));
				}
			}
		}

		return minArea == INT_MAX ? 0 : minArea;
	}
};

//int main()
//{
//	vector<vector<int>> points;
//	
//	//[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
//	points.push_back({ 1, 1 });
//	points.push_back({ 1, 3 });
//	points.push_back({ 3, 1 });
//	points.push_back({ 3, 3 });
//	points.push_back({ 4, 1 });
//	points.push_back({ 4, 3 });
//
//	Solution s;
//	auto result = s.minAreaRect(points);
//
//	return 0;
//}